Solving 10385 - Duathlon (Ternary search)
[andmenj-acm.git] / 11481 - Arrange the Numbers / explicación / e.tex
blobfcc6a675ee0a4f548a939067c070213119d7a0c1
1 \documentclass[10pt,letterpaper]{article}
3 %---------------------------------------------------------------
4 \usepackage[utf8]{inputenc}
5 \usepackage[spanish]{babel}
6 \usepackage{listings}
7 \usepackage[usenames,dvipsnames]{color}
8 \usepackage{amsmath}
9 \usepackage{amsthm}
10 \usepackage{amssymb}
11 %\usepackage{color}
12 %---------------------------------------------------------------
14 \setlength{\topmargin}{-1.0in}
15 \setlength{\textheight}{9.5in}
16 \setlength{\evensidemargin}{0.0in}
17 \setlength{\oddsidemargin}{0.0in}
18 \setlength{\textwidth}{6.5in}
20 \begin{document}
22 La respuesta es
24 {m \choose k} \cdot \displaystyle \sum_{i=0}^{m-k} (-1)^{i} {m - k \choose i} (n-k-i)!
27 \bigskip
29 \textbf{Explicación:} Lo primero que hacemos es escoger los $k$ elementos que quedarán ``clavados'' en su sitio correcto. Esto se puede hacer de $ {m \choose k} $ maneras diferentes, pues cualquier subconjunto de $k$ elementos entre los primeros $m$ elementos sirve para este propósito. \\
31 Ahora bien, por cada una de estas clavadas nos quedan $ n - k $ elementos por ubicar. Hay que hacerlo de manera que en las primeras $ m - k $ posiciones ningún elemento quede en su sitio, porque si sucede lo contrario entonces habrá mas elementos clavados en su sitio de los $k$ pedidos. Para contar cuántas permutaciones de $n-k$ elementos cumplen esto, utilizamos el principio de inclusión-exclusión\footnote {Bastante similar a la demostración del teorema 2, ``Número de permutaciones completas'', Sección 6.6: \textit{Aplicaciones del principio de inclusión-exclusión}, Capítulo 6: \textit{Técnicas avanzadas de recuento}, página 430, del libro \textbf{Matemáticas discretas y sus aplicaciones}, Kenneth Rosen, quinta edición, McGraw-Hill.}. El resultado es la sumatoria que multiplica a ${ m \choose k}$.\\
33 \begin{proof}{}
34 Decimos que una permutación tiene la propiedad $P_{i}$ si deja en su sitio el elemento $i$. El número que se busca es el número de permutaciones de $n - k$ elementos que no tiene la propiedad $P_{i}$ para $i=1, 2, \cdots , m - k$ y lo denotamos $ D = N(\bar{P_{1}} \bar{P_{2}} \cdots \bar{P}_{m-k}) $. Aplicando el principio de inclusión-exclusión tenemos que:\\
36 D = N - \sum_{i}{N(P_{i})} + \sum_{i < j}{N(P_{i}P_{j})} - \sum_{i < j < k}{N(P_{i}P_{j}P_{k})} + \cdots + (-1)^{m-k}N(P_{1}P_{2} \cdots P_{m-k})
39 Vemos que $$ N = (n-k)! $$ pues $N$ es la cantidad de permutaciones posibles.\\
40 Así mismo, $$ \sum_{i}{N(P_{i})} = { m - k \choose 1 } (n -k -1)! $$ Esto es, clavamos un sólo elemento de los primeros $m - k$ posibles, y el resto los permutamos de cualquier manera posible. Pero al restar estos elementos, restamos dos veces las permutaciones que tienen dos elementos fijos, así que las volvemos a sumar:
41 $$\sum_{i < j}{N(P_{i}P_{j})} = { m - k \choose 2 } (n -k -2)! $$
42 Esto es, clavamos dos elementos y el resto los permutamos de cualquier manera posible.\\
43 Y en general,
44 $$\sum{N(P_{i_{1}}P_{i_{2}} \cdots P_{i_{r}})} = { m - k \choose r } (n -k -r)! $$
45 Reemplazando estos términos en la ecuación original, obtenemos
47 D = N - \sum_{i}{N(P_{i})} + \sum_{i < j}{N(P_{i}P_{j})} - \sum_{i < j < k}{N(P_{i}P_{j}P_{k})} + \cdots + (-1)^{m-k}N(P_{1}P_{2} \cdots P_{m-k}) $$
49 = (n - k)! - { m - k \choose 1 } (n -k -1)! + { m - k \choose 2 } (n -k -2)! -
50 \cdots + (-1)^{m-k} { m - k \choose m - k } (n -k -(m - k))!
53 = \sum_{i=0}^{m-k} (-1)^{i} {m - k \choose i} (n-k-i)!
55 \end{proof}
56 \end{document}